package com.example.dynamicprogramming;

/**
 * 最少硬币组合问题
 */
public class MinCoins {
    public static void main(String[] args) {
        System.out.println(minCoins(new int[]{1,10,25}, 30));
    }
    public static int minCoins(int[] arr,int m){
        int[] f=new int[m+1];
        int n= arr.length;
        f[0]=0;
        for (int i = 1; i <m+1 ; i++) {
            f[i]=Integer.MAX_VALUE;
            for (int j = 0; j < n; j++) {
                if(i>=arr[j] && f[i-arr[j]]!=Integer.MAX_VALUE){
                    f[i]=Math.min(f[i],f[i-arr[j]]+1 );
                }
            }
        }
        return f[m];
    }
}
